package algorithm.sort;

import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;

/**
 * 计数排序
 * 计数排序平均时间复杂度：o(n+k)(平方)、空间复杂度：o(k)、稳定排序、外部排序
 * 利用 数据的下标进行排序
 */
public class CountSort {

    private static final int[] arr = new int[10];

    @Before
    public void init() {
        for (int i = 0, j = arr.length; i < j; i++) {
            arr[i] = (int) (Math.random() * 1000);
        }
    }

    @Test
    public void sort() {
        System.out.println("排序前：" + Arrays.toString(arr));
        //计算出数据中最大的数字
        int max = arr[0];
        for (int i = 1, len = arr.length; i < len; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }

        int[] temp = new int[max + 1];
        for (int k : arr) {
            temp[k]++;
        }

        int j = 0;
        for (int k = 0, len = temp.length; k < len; k++) {
            if (temp[k] == 1) {
                arr[j++] = k;
            }
        }
        System.out.println("排序后：" + Arrays.toString(arr));
    }

}
